import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-06-06
 * Time: 22:42
 */
public class LeetCode {
    // 1. 反转字符串中的单词
    public static String reverseWords(String s) {
        List<String> list = new LinkedList<>();
        int i = 0;
        while (i != s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
            } else {
                int tmp = i;
                while (i != s.length() && s.charAt(i) != ' ') {
                    i++;
                }
                String ret = s.substring(tmp, i);
                list.add(ret);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int j = list.size() - 1; j > 0; j--) {
            sb.append(list.get(j));
            sb.append(' ');
        }
        sb.append(list.get(0));
        return sb.toString();
    }

    public static void main1(String[] args) {
        String test = "a good   example";
        String result = reverseWords(test);
        System.out.println(result);
    }

    // 2. 递增的三元子序列
    // 这题我抄的答案！！！
    public static boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }

    public static void main2(String[] args) {
        int[] array = {2, 1, 5, 0, 4, 6};
        System.out.println(increasingTriplet(array));
    }


    // 3. 压缩字符串
    // 这里写了一个计算数字位数的方法
    public static int numCount(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n /= 10;
        }
        return count;
    }

    public static int compress(char[] chars) {
        int i = 0;
        int count = 0;
        int index = 0;
        while (i < chars.length) {
            int tmpCount = 1;
            while (i + 1 < chars.length && chars[i + 1] == chars[i]) {
                tmpCount++;
                i++;
            }
            char tmpChar = chars[i];
            chars[index++] = tmpChar;

            // 此时tmpCount里面记录的就是当前重复字符的个数
            if (tmpCount == 1) {
                count++;
            } else if (tmpCount < 10) {
                chars[index++] = (char) (tmpCount + '0');
                count += 2;
            } else {
                int len = numCount(tmpCount) + 1;
                count += len;

                List<Character> list = new ArrayList<>();
                while (tmpCount > 0) {
                    list.add((char) (tmpCount % 10 + '0'));
                    tmpCount /= 10;
                }
                for (int j = list.size() - 1; j >= 0; j--) {
                    chars[index++] = list.get(j);
                }

            }
            i++;
        }
        return count;
    }

    public static void main3(String[] args) {
        char[] chars1 = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};
        char[] chars2 = {'a'};
        char[] chars3 = {'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'};
        System.out.println(compress(chars3));
        System.out.println("---------------------");
        int len = compress(chars3);
        for (int i = 0; i < len; i++) {
            System.out.println(chars3[i]);
        }
    }


    // 4.盛最多水的容器(双指针)
    public static int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int max = 0;
        while (start != end) {
            // 两个指针指向的数字中较小值 ∗ 指针之间的距离
            int ret = height[start] < height[end] ? height[start] : height[end];
            int len = end - start;
            int tmpMax = ret * len;
            if (tmpMax > max) {
                max = tmpMax;
            }
            if (height[start] == ret) {
                start++;
            } else {
                end--;
            }

        }
        return max;
    }

    public static void main4(String[] args) {
        int[] array = {1, 1};
        int result = maxArea(array);
        System.out.println(result);
    }

    // 5.K 和数对的最大数目
    // 核心是排序！！！
    public static int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);

        int res = 0;
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            long val = nums[left] + nums[right];

            // 大于目标值则右边界移动
            if (val > k) {
                --right;
            }
            // 小于目标值则左区间移动
            else if (val < k) {
                ++left;
            } else {
                ++res;
                ++left;
                --right;
            }
        }
        return res;
    }

    public static void main5(String[] args) {
        int[] array = {1, 2, 3, 4};
        System.out.println(maxOperations(array, 5));
    }


    // 6.定长子串中元音的最大数目
    public boolean isIn(char x) {
        if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
            return true;
        }
        return false;
    }

    public int maxVowels(String s, int k) {
        int maxCount = 0;
        for (int i = 0; i < k; i++) {
            if (isIn(s.charAt(i))) {
                maxCount++;
            }
        }
        int left = 0;
        int right = k;
        int tmpCount = maxCount;
        while (right < s.length()) {
            if (isIn(s.charAt(left))) {
                tmpCount--;
            }
            if (isIn(s.charAt(right))) {
                tmpCount++;
            }
            if (tmpCount > maxCount) {
                maxCount = tmpCount;
            }
            left++;
            right++;
        }
        return maxCount;

    }

    // 7.子数组最大平均数 I
    public double findMaxAverage(int[] nums, int k) {
        int left = 0;
        int right = k;
        double maxAvg = 0;

        int tmpSum = 0;
        for (int i = 0; i < k; i++) {
            tmpSum += nums[i];
        }
        maxAvg = tmpSum / (double) k;

        double tmpAvg = 0;
        while (right < nums.length) {
            tmpSum -= nums[left];
            tmpSum += nums[right];
            tmpAvg = tmpSum / (double) k;
            if (tmpAvg > maxAvg) {
                maxAvg = tmpAvg;
            }
            left++;
            right++;
        }
        return maxAvg;

    }

    // 8.找到最高海拔
    public int largestAltitude(int[] gain) {
        int max = 0;
        int ret = 0;
        for (int i = 0; i < gain.length; i++) {
            ret += gain[i];
            if (ret > max) {
                max = ret;
            }
        }
        return max;
    }

    // 9.寻找峰值
    public int findPeakElement(int[] nums) {
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        // 处理数组长度为 1 时的情况
        if (nums.length == 1) {
            return 0;
        }
        // 处理数组长度 >= 2 时 并且 中间不存在峰值
        if (nums[0] > nums[1]) {
            // 递减 返回首元素
            return 0;
        } else {
            // 递增 返回首元素
            return nums.length - 1;
        }
    }

    // 10.从字符串中移除星号
    // 错误版本（使用栈，从后往前遍历）
//    public static String removeStars(String s) {
//        Deque<Character> queue = new ArrayDeque<>();
//        int i = s.length() - 1;
//        while (i >= 0) {
//            if (s.charAt(i) == '*') {
//                int count = 0;
//                int tmp = i;
//                while (s.charAt(tmp) == '*') {
//                    count ++;
//                    tmp --;
//                }
//                i -= count*2;
//            } else {
//                queue.push(s.charAt(i));
//                i --;
//            }
//        }
//        StringBuilder sb = new StringBuilder();
//        while (!queue.isEmpty()) {
//            sb.append(queue.pop());
//        }
//        return sb.toString();
//    }

    // 换一种思路（从前往后遍历）
    public static String removeStars(String s) {
        Deque<Character> queue = new ArrayDeque<>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '*') {
                queue.pop();
                i++;
            } else {
                queue.push(s.charAt(i));
                i++;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            sb.append(queue.pop());
        }
        return sb.reverse().toString();
    }

    public static void main10(String[] args) {
        String test = "erase*****";
        System.out.println(removeStars(test));
    }

    // *** Dota2 参议院 *** 请仔细分析大佬的思路！！！
    public String predictPartyVictory(String senate) {
        int Rnumber = 0;//R阵营总人数
        int Dnumber = 0;//D阵营总人数
        int curBanR = 0;//当前被ban
        int curBanD = 0;//当前被ban
        int totalBanR = 0;//被ban总数
        int totalBanD = 0;//被ban总数
        char[] chars = senate.toCharArray();
        boolean flag = true;
        while (true) {
            for (int i = 0; i < chars.length; i++) {
                char cur = chars[i];
                if (cur == 'R') {
                    if (flag)
                        Rnumber++;
                    if (curBanR == 0) {
                        curBanD++;
                        totalBanD++;
                        if (totalBanD == Dnumber && !flag) return "Radiant";
                    } else {
                        curBanR--;
                        chars[i] = 'r';
                    }
                } else if (cur == 'D') {
                    if (flag)
                        Dnumber++;
                    if (curBanD == 0) {
                        curBanR++;
                        totalBanR++;
                        if (totalBanR == Rnumber && !flag) return "Dire";
                    } else {
                        curBanD--;
                        chars[i] = 'd';
                    }
                }
            }
            flag = false;
            if (totalBanD >= Dnumber) return "Radiant";
            if (totalBanR >= Rnumber) return "Dire";
        }
    }

    // ----------------------------------- 剑指Offer -----------------------------------------
    // No.1：剑指 Offer 05. 替换空格
    public String replaceSpace(String s) {
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
            i++;
        }
        return sb.toString();
    }


    // No.2：剑指 Offer 58 - II. 左旋转字符串
    // 这里写一个反转字符串的方法：reverseString
    public void reverseString(char[] array, int start, int end) {
        while (start < end) {
            char tmp = array[start];
            array[start] = array[end];
            array[end] = tmp;
            start++;
            end--;
        }
    }

    public String reverseLeftWords(String s, int n) {
        // 方法一：暴力左旋（库函数版本）
        // StringBuilder sb = new StringBuilder();
        // String sBack = s.substring(n);
        // String sBefore = s.substring(0,n);
        // sb.append(sBack);
        // sb.append(sBefore);
        // return sb.toString();

        // 方法二：暴力左旋（两次反转字符串）

        char[] array = s.toCharArray();
        // 1.反转整个字符串
        reverseString(array, 0, array.length - 1);
        // 2.反转前半部分
        reverseString(array, 0, array.length - 1 - n);
        // 3.反转后半部分
        reverseString(array, array.length - 1 - n + 1, array.length - 1);
        return String.valueOf(array);

    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    // No.3：剑指 Offer 24. 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    // No.4：剑指 Offer 06. 从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        Deque<Integer> stack = new ArrayDeque<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] array = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()) {
            int x = stack.pop();
            array[i++] = x;
        }
        return array;
    }

    // No.4：剑指 Offer 20. 表示数值的字符串
    public boolean isNumber(String s) {
        if (s.length() == 0) {
            return false;
        }
        // 删去前后空格
        String ss = s.trim();
        if (ss.length() == 0) {
            return false;
        }
        // 处理字符串前缀
        int pointNum = 0;
        int flag = 1;
        if (ss.charAt(0) == '+' || ss.charAt(0) == '-') {
            if (ss.length() == 1) {
                return false;
            }
            // 处理+ - 号
            flag = isPositive(ss.charAt(0));
            ss = ss.substring(1);

            // 进一步处理 .
            if (ss.charAt(0) == '.') {
                pointNum++;
                if (ss.length() == 1) {
                    return false;
                }
                ss = ss.substring(1);
            }

        } else if (ss.charAt(0) == '.') {
            pointNum++;
            if (ss.length() == 1) {
                return false;
            }
            // 处理 .
            ss = ss.substring(1);
        }
        // 拿到处理完前缀的字符串
        // 如果此时第一个字符不是数字

        int fig = 0;
        if (!Character.isDigit(ss.charAt(0))) {
            return false;
        } else {
            int i = 0;
            while (i < ss.length()) {
                if (Character.isDigit(ss.charAt(i))) {
                    i++;
                } else if (ss.charAt(i) == 'e' || ss.charAt(i) == 'E') {
                    fig++;
                    if (fig > 1) {
                        return false;
                    }
                    i++;
                    if (i < ss.length()) {
                        if (ss.charAt(i) == '-' || ss.charAt(i) == '+') {
                            i++;
                            if (i < ss.length() && Character.isDigit(ss.charAt(i))) {
                                i++;
                            } else {
                                return false;
                            }
                        } else {
                            if (Character.isDigit(ss.charAt(i))) {
                                i++;
                            } else {
                                return false;
                            }
                        }
                    } else {
                        return false;
                    }
                } else if (ss.charAt(i) == '.') {
                    if (fig > 0) {
                        return false;
                    }
                    pointNum++;
                    if (pointNum == 2) {
                        return false;
                    }
                    i++;
                    if (i < ss.length()) {
                        if (Character.isDigit(ss.charAt(i))) {
                            i++;
                        } else if (ss.charAt(i) == 'e' || ss.charAt(i) == 'E') {
                            i++;
                            if (i >= ss.length()) {
                                return false;
                            } else {
                                i--;
                            }
                        } else {
                            return false;
                        }
                    } else {
                        return true;
                    }
                } else {
                    return false;
                }
            }
            return true;
        }
    }

    private int isPositive(char ch) {
        if (ch == '+') {
            return 1;
        } else {
            return -1;
        }
    }

    // 剑指 Offer 67. 把字符串转换成整数
    public static int strToInt(String str) {
        // 去除字符串首尾空格
        str = str.trim();
        // 字符串为空
        if (str.length() == 0) {
            return 0;
        }
        // 判断是否存在正负号
        // flag为符号位,默认为+1
        int flag = 1;
        char head = str.charAt(0);
        if (head == '-') {
            // 如果处理完符号后字符串长度为空
            if (str.length() == 1) {
                return 0;
            }
            flag = -1;
            // 去除符号位
            str = str.substring(1);
        } else if (head == '+') {
            // 如果处理完符号后字符串长度为空
            if (str.length() == 1) {
                return 0;
            }
            flag = 1;
            // 去除符号位
            str = str.substring(1);
        } else if (!Character.isDigit(head)) {
            // 既不是正负号也不是数字
            return 0;
        }
        // 处理完正负号，判断下一位是否为数字
        if (!Character.isDigit(str.charAt(0))) {
            return 0;
        }

        // 下面是正常处理数字的情况
        long num = flag * transfer(str.charAt(0));
        int i = 1;
        while (i < str.length() && Character.isDigit(str.charAt(i))) {
            int newNum = transfer(str.charAt(i));
            // 构造新num数
            num = num * 10 + (newNum * flag);
            // 判断当前num数值与INT_MIN和INT_MAX的关系
            if (num < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            if (num > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            i++;
        }
        // 上面都没返回，最后返回num值
        return (int) num;
    }

    // 整数字符转整数
    private static int transfer(char ch) {
        return (int) (ch - '0');
    }

//    public static void main(String[] args) {
//        System.out.println(strToInt("-91283472332"));
//    }

    // 80. 删除有序数组中的重复项 II
    public static int removeDuplicates(int[] nums) {
        int ret = nums[0];
        int i = 0;
        // len是随着数组长度动态变化的，设为全局变量
        int len = nums.length;
        while (i < len) {
            // 用来标识偏移量
            int width = 0;
            // 用来统计重复数量
            int count = 0;
            // 统计当前数字重复次数
            while (i < len && nums[i] == ret) {
                i++;
                count++;
            }
            // 此时i的位置来到非重复数字的那一位
            // 如果重复次数大于3就进行移动操作
            if (count >= 3) {
                // 根据重复次数计算偏移量
                width = count - 2;
                // 设置临时变量tmpI，便于进行移位，而不影响全局变量i
                int tmpI = i;
                while (tmpI < len) {
                    nums[tmpI - width] = nums[tmpI];
                    tmpI++;
                }
                // 更新数组长度
                len -= width;
                // 更新i的实际位置
                i -= width;
            }
            // 下一轮开始，初始化ret值
            // 注意由于 i 最终位置可能出界，这里需要提前判断一下
            if (i < len) {
                ret = nums[i];
            }
        }
        return len;
    }

    public static void main6(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 1, 2, 3, 3};
        System.out.println(removeDuplicates(nums));
        System.out.println("hehe");
    }

    // 189. 轮转数组
    // 复杂度太高
    // 时间复杂度为O(N*K)
    public static void rotate1(int[] nums, int k) {
        // 处理数组长度为1的情况
        if (nums.length == 1) {
            return;
        }
        // 按照题意暴力解题
        while (k != 0) {
            // 数组长度
            int len = nums.length - 1;
            // 记录轮转数值
            int targetNum = nums[len];
            // 开始轮转
            while (len >= 1) {
                nums[len] = nums[len - 1];
                len--;
            }
            // 更换第一位数
            nums[0] = targetNum;
            k--;
        }
    }

    // 方案二：三次旋转
    // 数组旋转函数
    // 时间复杂度为O(N)
    private static void arrayRoate(int[] nums, int left, int right) {
        while (left <= right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }

    public static void rotate(int[] nums, int k) {
        // 处理数组长度为1的情况
        if (nums.length == 1) {
            return;
        }
        // 这一步很关键：经分析当轮次k == nums.length时，数组不变
        k %= nums.length;
        // 左分片旋转
        int left_l = 0;
        int right_l = nums.length - 1 - k;
        arrayRoate(nums, left_l, right_l);
        // 右分片旋转
        int left_r = nums.length - 1 - k + 1;
        int right_r = nums.length - 1;
        arrayRoate(nums, left_r, right_r);
        // 整个数组旋转
        arrayRoate(nums, 0, nums.length - 1);
    }

    public static void main11(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int[] nums2 = {-1, -100, 3, 99};
        rotate(nums, 8);
        System.out.println(Arrays.toString(nums));

    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    // 剑指 Offer 35. 复杂链表的复制
    public Node copyRandomList(Node head) {
        // 判空
        if (head == null) {
            return null;
        }
        // 初步解题思想，遍历两遍链表
        Node curCopy = new Node(head.val);
        Node flag = curCopy;
        Node cur = head.next;
        // 1.第一遍遍历确定复制后链表的next结点
        while (cur != null) {
            Node newNode = new Node(cur.val);
            curCopy.next = newNode;
            cur = cur.next;
            curCopy = curCopy.next;
        }
        // 同步
        cur = head;
        curCopy = flag;
        // 2.第二遍遍历确定复制后链表的random结点
        while (cur != null) {
            Node ranNode = getPosition(head, cur.random, flag);
            curCopy.random = ranNode;
            cur = cur.next;
            curCopy = curCopy.next;
        }
        return flag;

    }

    public Node getPosition(Node head, Node random, Node flag) {
        while (head != random) {
            head = head.next;
            flag = flag.next;
        }
        return flag;
    }

    // 1657. 确定两个字符串是否接近
    public static boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < word2.length(); i++) {
            char w1 = word1.charAt(i);
            char w2 = word2.charAt(i);
            if (map1.containsKey(w1)) {
                int n = map1.get(w1);
                map1.put(w1, n + 1);
            } else {
                map1.put(w1, 0);
            }
            if (map2.containsKey(w2)) {
                int n = map2.get(w2);
                map2.put(w2, n + 1);
            } else {
                map2.put(w2, 0);
            }
        }
        if (map1.size() != map2.size()) {
            return false;
        }
        Set<Character> set1 = map1.keySet();
        Set<Character> set2 = map2.keySet();
        if (!set1.containsAll(set2)) {
            return false;
        }


        List<Integer> sortedList1 = new ArrayList<>(map1.values());
        List<Integer> sortedList2 = new ArrayList<>(map2.values());
        Collections.sort(sortedList1);
        Collections.sort(sortedList2);

        for (int i = 0; i < sortedList1.size(); i++) {
            if (!sortedList1.get(i).equals(sortedList2.get(i))) {
                System.out.println(sortedList1.get(i));
                System.out.println(sortedList2.get(i));
                return false;
            }
        }

        return true;
    }

    public static void main15(String[] args) {
        int a = 1000;
        Integer b = 1000;
        // 自动拆箱，将Integer转化为int类型
        System.out.println(a == b);

    }

    // 129. 求根节点到叶节点数字之和
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int sumNumbers(TreeNode root) {
        // 要学会变通，感觉缺少参数可以添加一个接口方法
        return helper(root, 0);
    }

    public int helper(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }
        int tmp = i * 10 + root.val;
        if (root.left == null && root.right == null) {
            return tmp;
        }
        return helper(root.left, tmp) + helper(root.right, tmp);
    }

    // 112. 路径总和
    // 看题解真是太巧妙了
    class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) {
                return false;
            }
            if (root.left == null && root.right == null) {
                return sum == root.val;
            }
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }

    }

    // 173. 二叉搜索树迭代器
    class BSTIterator {
        List<Integer> inorderList = new LinkedList<>();
        int index;

        public BSTIterator(TreeNode root) {
            inorderList.add(null);
            index = 0;
            inorder(root);
        }

        private void inorder(TreeNode root) {
            if (root == null) {
                return;
            }
            inorder(root.left);
            inorderList.add(root.val);
            inorder(root.right);
        }

        public int next() {
            if (hasNext()) {
                return inorderList.get(++index);
            }
            return -1;
        }

        public boolean hasNext() {
            if (index + 1 < inorderList.size()) {
                return true;
            } else {
                return false;
            }
        }
    }

    // 49. 字母异位词分组
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);


            if (map.containsKey(key)) {
                map.get(key).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        List<List<String>> lists = new ArrayList<>(map.values());
        return lists;

    }

    public static void main17(String[] args) {
        String[] array = {"eat", "tea", "tan", "ate", "nat", "bat"};
        groupAnagrams(array);
    }


    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int head = 0;
        int last = nums.length - 1;

        List<List<Integer>> three = new ArrayList<>();

        int i = 0;
        while (i < nums.length) {
            if (i >= 1 && nums[i] == nums[i - 1]) {
                i++;
                continue;
            }

            int target = (-1) * nums[i];
            if (i + 1 < nums.length - 2) {
                getTwo(three, target, i, i + 1, nums.length - 1, nums);
            }
            i++;
        }
        return three;
    }

    private void getTwo(List<List<Integer>> three, int target, int targetIndex, int left, int right, int[] nums) {
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[targetIndex]);
                list.add(nums[left]);
                list.add(nums[right]);
                three.add(list);

                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }

            } else if (sum < target) {
                left++;

            } else if (sum > target) {
                right--;
            }
        }
    }

    // 122. 买卖股票的最佳时机 II
    // 8-17 贪心这么酷吗？
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

    // 92. 反转链表 II（这题感觉有点吃力，再好好看看反转这块）
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        // 需要找到 left -1 结点 和 right + 1 结点
        ListNode curLeft = head;
        ListNode leftP = null;
        int tmpL = left;
        while (tmpL > 1) {
            leftP = curLeft;
            curLeft = curLeft.next;
            tmpL--;
        }
        int tmpR = right;
        ListNode curRight = head;
        ListNode rightN = null;
        while (tmpR > 1) {
            curRight = curRight.next;
            tmpR--;
        }
        rightN = curRight.next;
        if (left == 1) {
            head = curRight;
        }

        reverseList(curLeft, curRight, leftP, rightN);
        return head;
    }

    private void reverseList(ListNode left, ListNode right, ListNode leftP, ListNode rightN) {
        ListNode pre = left;
        ListNode cur = left.next;
        while (cur != rightN) {
            ListNode curNext = cur.next;
            cur.next = pre;

            pre = cur;
            cur = curNext;

        }
        left.next = rightN;
        if (leftP != null) {
            leftP.next = right;
        }
    }

    // 14.最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        String first = strs[0];
        int n = first.length();
        StringBuilder result = new StringBuilder();
        for (int i = 1; i < strs.length; i++) {
            String ret = strs[i];
            int len1 = first.length();
            int len2 = ret.length();
            int len = len1 < len2 ? len1 : len2;
            int j = 0;
            int m = 0;
            while (j < len) {
                if (ret.charAt(j) == first.charAt(j)) {
                    m++;
                } else {
                    break;
                }
                j++;
            }
            if (m < n) {
                n = m;
            }
        }
        String pic = first.substring(0, n);
        result.append(pic);
        return result.toString();
    }


    // 71. 简化路径
    public static String simplifyPath(String path) {
        Deque<String> vector = new LinkedList<>();

        vector.push("/");
        // 1.入栈
        int i = 1;
        while (i < path.length()) {
            // 如果存在多个//需要处理
            while (i < path.length() && path.charAt(i) == '/') {
                i++;
            }
            // 找到下一级目录
            int star = i;
            while (i < path.length() && path.charAt(i) != '/') {
                i++;
            }
            int end = i;
            // 如果是最后一级目录需要处理最后的'/'
            String dire = "";
            if (i < path.length()) {
                dire = path.substring(star, end + 1);
            } else {
                dire = path.substring(star);
            }
            i++;
            // 入栈,出栈

            if (dire.equals("../") || dire.equals("..")) {
                if (vector.size() > 1) {
                    vector.pop();
                }
            } else if (!dire.equals("./") && !dire.equals(".")) {
                vector.push(dire);
            }
        }
        // 出队
        StringBuilder sbuider = new StringBuilder();
        while (!vector.isEmpty()) {
            sbuider.append(vector.pollLast());
        }
        if (sbuider.length() > 1 && sbuider.charAt(sbuider.length() - 1) == '/') {
            sbuider.delete(sbuider.length() - 1, sbuider.length());
        }
        return sbuider.toString();

    }

    public static void main18(String[] args) {
        simplifyPath("/a//b////c/d//././/..");
    }


    // 面试题 17.04. 消失的数字
    public int missingNumber(int[] nums) {
        // 这一题使用异或超出真的是太妙了！！！
        int miss = 0;
        for (int i = 0; i < nums.length; i ++) {
            miss ^= nums[i];
        }
        for (int i = 0; i <= nums.length; i ++) {
            miss ^= i;
        }
        return miss;
    }

    // 189. 轮转数组
    public void rotate8(int[] nums, int k) {
        // 1. 反转整个数组
        reverse(nums,0,nums.length - 1);

        // 2. 反转 0 ~ k % n - 1
        reverse(nums,0,k%nums.length -1);

        // 3. 反转 k % n ~ n - 1
        reverse(nums,k%nums.length,nums.length - 1);
    }
    private void reverse(int[] arr,int start,int end) {
        while (start < end) {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start ++;
            end --;
        }
    }





    // 121.买卖股票的最佳时机[暴力必超时！]
    public int maxProfit1(int[] prices) {
        // 暴力法
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i] > maxprofit) {
                    maxprofit = prices[j] - prices[i];
                }
            }
        }
        return maxprofit;
    }

    // 正确答案
    public int maxProfit2(int[] prices) {
        int minvalue = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i ++) {
            // 记录史低
            if (prices[i] < minvalue) {
                minvalue = prices[i];
            } else if (prices[i] - minvalue > maxProfit) {
                maxProfit = prices[i] -  minvalue;
            }
        }
        return maxProfit;
    }

    // 二叉树的前中后遍历
    public void preOrder(TreeNode root,List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);

    }
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList();
        preOrder(root,list);
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i ++) {
            arr[i] = list.get(i);
        }
        return arr;

    }


}
